算法题之Number Sequence

文章目录

1. 1. 题目
2. 2. 解答
   1. 2.1. C语言实现
   2. 2.2. C++实现

题目

杭电acm题目：http://acm.hdu.edu.cn/showproblem.php?pid=1003

解答

以下为在杭电hdu acm上已AC的C语言、C++实现的两种方法

C语言实现

#include<stdio.h>
int f[10000];
int main(){
    int A,B,n;
    f[1]=f[2]=1;
    while(scanf("%d%d%d",&A,&B,&n),A||B||n){
        int i;
        for(i=3;i<10000;i++){
            f[i]=(A*f[i-1]+B*f[i-2])%7;
            if(f[i]==1&&f[i-1]==1)
                break;
        }
        n=n%(i-2);
        f[0]=f[i-2];
        printf("%d\n",f[n]);
    }
    return 0;
}

C++实现

#include <iostream>   
using namespace std;  
  
int arr[10000];   
   
int main()  
{  
    int A,B,n;  
    arr[1] = arr[2] = 1;  
    while(cin>>A>>B>>n, A || B || n)  
    {  
        int i;  
        for(i=3; i<10000 ;i++)  
        {  
            arr[i] = (A*arr[i-1] + B*arr[i-2]) % 7;  
              
            //如果有两个连着 =1，则后面的全部和前面相同，即出现了周期   
            //这时就没必要再进行下去了，跳出循环, i-2为周期    
            if(arr[i] == 1 && arr[i-1] == 1)              
                break;  
        }  
        n = n % (i-2);  
          
        // 把n对周期求模，当n = i-2时, n=0,此时本来应该取arr[i-2]的，所以把arr[0]=arr[i-2]    
        //也可以这样：   
        //if(n==0)   n=i-2;                   
        arr[0] = arr[i-2];    
        cout << arr[n] << endl;  
    }  
    return 0;  
}